//给定一个整数数组 prices，其中第 prices[i] 表示第 i 天的股票价格 。 
//
// 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 
//
// 
// 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 
// 
//
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 
//
// 
//
// 示例 1: 
//
// 
//输入: prices = [1,2,3,0,2]
//输出: 3 
//解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 
//
// 示例 2: 
//
// 
//输入: prices = [1]
//输出: 0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= prices.length <= 5000 
// 0 <= prices[i] <= 1000 
// 
// Related Topics 数组 动态规划 👍 1193 👎 0

package leetcode.editor.cn;

class BestTimeToBuyAndSellStockWithCooldown {
    public static void main(String[] args) {
        Solution solution = new BestTimeToBuyAndSellStockWithCooldown().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxProfit(int[] prices) {
            // 分为4个状态
            // 状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）
            // 卖出股票状态，这里就有两种卖出股票状态
            //   状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
            //   状态三：今天卖出了股票
            // 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！

            // dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。
            int[][] dp = new int[prices.length][4];
            dp[0][0] -= prices[0];  // 今天买入的话
            dp[0][1] = 0;   // 第0天没有卖出
            dp[0][2] = 0;   // 第0天卖出股票，也是相当于买入卖出，而且最小的利润是0，所以初始化为0
            dp[0][3] = 0;   // 第0天没有卖出，也就没有冷冻期

            for (int i = 1; i < prices.length; i++) {
                // 持有股票有2个操作：(都取最大的利润)
                //      操作一：昨天就是持有股票的状态，也就是昨天才买入(状态一)
                //      操作二：1.昨天已经卖出股票很多天了，几天可以买入(状态二) 2.昨天时冷冻期，但今天可以买入(状态四)
                dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1] - prices[i], dp[i - 1][3] - prices[i]));
                //  卖出股票状态：(都取最大利润)
                //      操作一：昨天就是卖出股票的状态(状态二)
                //      操作二：昨天就是冷冻期(状态四)
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);
                // 今天正好卖出股票：也就是昨天刚买入，今天才能卖出
                dp[i][2] = dp[i - 1][0] + prices[i];
                // 冷冻期状态：昨天才卖出，今天才是冷冻期
                dp[i][3] = dp[i - 1][2];
            }

            // 在冷冻期，卖出股票状态，正好卖出状态取最大的利润
            return Math.max(dp[prices.length - 1][1], Math.max(dp[prices.length - 1][2], dp[prices.length - 1][3]));
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
